import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-06-03
 * Time: 16:44
 */
public class TEST01 {
    //堆排序
    public static void shiftDown(int []arr,int root,int size) {
        int parents = root;
        int child = 2*parents +1;
        //进这个循环说明有孩子节点
        while( child < size) {
            //找到左右孩子的最大值
            //保证有右孩子
            if( child + 1 < size && arr[child] < arr[child+1]) {
                child++;
            }
            //此时child放的左右孩子的最大值的下标 , 与父亲节点进行比较,比其大进行交换
            if( arr[child] > arr[parents]) {
                int tmp = arr[child];
                arr[child] = arr[parents];
                arr[parents] = tmp;

                //交换完毕后更新下标
                parents = child;
                child = parents * 2 +1;
            } else {
                break;
            }
        }
    }
    //建堆
    public static void createHeap(int []arr) {
         int p;
         int len = arr.length;
         for( p= (len - 1 -1)/2 ;p>=0;p--) {
             shiftDown(arr,p,len);
         }
    }
    //堆排序
    public static void heapSort( int []arr) {
        createHeap(arr);
        int end = arr.length -1;
        while(end>=0) {
            //交换0 位置和end位置的值
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
            //向下调整
            shiftDown(arr,0,end);
            end--;
        }
    }

    //插入排序
    public static void insertSort(int []arr) {
        int i,j;
        for (i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            for (j = i-1; j >=0 ; j--) {
                if( arr[j] > tmp) {
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

    //选择排序
    public static void selectSort(int []arr) {
        int i,j;
        for(i=0;i<arr.length;i++) {
            for(j=i+1;j<arr.length;j++) {
                if(arr[j] < arr[i]) {
                    int tmp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = tmp;
                }
            }
        }
    }
//    //快速排序
//
//    public static void quickSort(int arr[] , int left ,int right) {
//        quickSort(arr,left,);
//    }
    public static void main(String[] args) {
        int []arr = { 8,7,6,556,4,3,2,4,110};
//        heapSort(arr);
//        insertSort(arr);
        selectSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
